package com.jack.leetcode.每日一题;

/*** 
 * @author zhangjie
 * @date 2020/4/19 21:45
 */
public class 统计重复个数 {

    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        int len1 = s1.length();
        int len2 = s2.length();

        if (len1 == 0 || len2 == 0 || n1 == 0 || n2 == 0) {
            return 0;
        }
        int index = 0;
        int count = 0;
        int[] countRecorder = new int[n1];
        int[] indexRecorder = new int[n1];
        for (int i = 0; i < n1; i++) {
            for (int j = 0; j < len1; j++) {
                if (s1.charAt(j) == s2.charAt(index)) {
                    ++index;
                }
                if (index == s2.length()) {
                    ++count;
                    index = 0;
                }
            }
            countRecorder[i] = count;
            indexRecorder[i] = index;
            for (int j = 0; j < i && indexRecorder[j] == index; j++) {
                int preCount = countRecorder[j];
                int patternCount = (n1 - 1 - j) / (i - j) * (countRecorder[i] - countRecorder[j]);
                int remainCount = countRecorder[j + (n1 - 1 - j) % (i - j)] - countRecorder[j];
                return (preCount + patternCount + remainCount) / n2;
            }
        }
        return countRecorder[n1 - 1] / n2;
    }
}
